package leetcode.number;

import leetcode.listnode.ListNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * 示例 1：
 * <p>
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 * <p>
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 * <p>
 * 限制：
 * 0 <= k <= arr.length <= 10000
 * 0 <= arr[i] <= 10000
 */
public class GetLeastNumbers {
    /**
     * 大顶堆
     * <p>
     * 大顶堆即最大堆。(或者叫大根堆) 最大堆是二叉堆的两种形式之一。
     * 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆.
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        // 使用一个最大堆（大顶堆）
        // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
        for (int i : arr) {
            if (heap.isEmpty() || heap.size() < k || i < heap.peek()) {
                heap.offer(i);
            }

            if (heap.size() > k) {
                //删除堆顶元素
                heap.poll();
            }
        }

        int[] result = new int[k];
        int index = 0;
        for (Integer integer : heap) {
            result[index++] = integer;
        }
        return result;
    }

    public int[] reversePrint(ListNode head) {
        Deque<ListNode> deque = new LinkedList<>();
        while (head != null) {
            deque.push(head);
            head = head.next;
        }

        int[] array = new int[deque.size()];
        int index = 0;
        while (deque.size() != 0) {
            array[index++] = deque.pop().val;
        }
        return array;
    }

    public String removeDuplicates(String s) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }

}
